/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/insert-interval
   @Language: C++
   @Datetime: 19-06-25 09:11
   */

// Method 1, Time O(n), Space O(1), Time 32ms
class Solution {
public:
	vector<vector<int> > insert(vector<vector<int> > &A, vector<int> &a) {
		int i=0, j=0;
		for(i=0; i<A.size() && a[0]>A[i][1]; ++i);
		for(j=i; j<A.size() && a[1]>=A[j][0]; ++j)
			a={min(a[0],A[j][0]), max(a[1],A[j][1])};
		A.insert(A.begin()+j,a);
		A.erase(A.begin()+i, A.begin()+j);
		return A;
	}
};

// Method 2, Time O(logn), Space O(1), Time 20ms
class Solution {
	static bool comp(const vector<int> &a, const vector<int> &b){
		return a[1]<b[0];
	}
public:
	vector<vector<int> > insert(vector<vector<int> > &A, vector<int> &a) {
		int i=lower_bound(A.begin(),A.end(),a,comp)-A.begin(), j=0;
		for(j=i; j<A.size() && a[1]>=A[j][0]; ++j)
			a={min(a[0],A[j][0]), max(a[1],A[j][1])};
		A.insert(A.begin()+j,a);
		A.erase(A.begin()+i, A.begin()+j);
		return A;
	}
};
